package LeetCode._01算法入门.day02双指针;


import org.junit.Test;

import java.util.Arrays;

/**
 * @author 挚爱之夕
 * @date 2022-02-21 - 02 - 21 - 16:32
 * @Description 给你一个按非递减顺序排序的整数数组nums，
 * 返回每个数字的平方组成的新数组，要求也按非递减顺序排序。
 * @Version 简单
 */
public class _977有序数组的平方 {
    static int[] nums = new int[]{-4,-1,0,3,10};

    /*by me*/
    @Test
    public void f1(){
        int[] res = sortedSquares(nums);
        Arrays.stream(res).forEach(System.out::println);
    }
    public static int[] sortedSquares(int[] nums) {
        //辅助空间
        int[] res = new int[nums.length];
        int index = 0;
        int p = findFirstNotNegative(nums);
        //双指针
        int left = p - 1;
        int right = p;
        int leftSquare;
        int rightSquare;
        //从中间向左右扫
        while (left >= 0 && right < nums.length) {
            leftSquare = nums[left] * nums[left];
            rightSquare = nums[right] * nums[right];
            if (leftSquare < rightSquare) {
                res[index++] = leftSquare;
                left--;
            } else {
                res[index++] = rightSquare;
                right++;
            }
        }
        //剩余了一边平方值较大
        while (left >= 0) {
            res[index++] = nums[left] * nums[left];
            left--;
        }
        while (right < nums.length) {
            res[index++] = nums[right] * nums[right];
            right++;
        }
        return res;
    }

    //找到第一个非负数，如果都是负数返回最后一个数下标
    private static int findFirstNotNegative(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= 0) {
                return i;
            }
        }
        return nums.length - 1;
    }
    /*官方思路*/
    //从中间向两边
    public static int[] sortedSquares1(int[] nums) {
        int n = nums.length;
        //寻找最大负数下标，如果没有是-1
        int negative = -1;
        for (int i = 0; i < n; ++i) {
            if (nums[i] < 0) {
                negative = i;
            } else {
                break;
            }
        }

        int[] ans = new int[n];
        int index = 0, i = negative, j = negative + 1;
        while (i >= 0 || j < n) {
            if (i < 0) {//左指针越界
                ans[index] = nums[j] * nums[j];
                ++j;
            } else if (j == n) {//右指针越界
                ans[index] = nums[i] * nums[i];
                --i;
            } else if (nums[i] * nums[i] < nums[j] * nums[j]) {//左边的平方小
                ans[index] = nums[i] * nums[i];
                --i;
            } else {//右边的平方小
                ans[index] = nums[j] * nums[j];
                ++j;
            }
            ++index;
        }

        return ans;
    }
    //从两边向中间扫，不用考虑下标越界情况,将较大的平方逆序存入
    public static int[] sortedSquares2(int[] nums) {
        int n = nums.length;
        int[] ans = new int[n];
        int left = 0, right = n - 1, pos = n - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                ans[pos] = nums[left] * nums[left];
                ++left;
            } else {
                ans[pos] = nums[right] * nums[right];
                --right;
            }
            --pos;
        }
        return ans;
    }
}
